In an In-Car Communication (ICC) system that supports speech communication between passengers, the signal recorded by the microphone(s) is processed and played back over one or more loudspeakers within the car. Communication can often be improved via noise reduction. Noise reduction typically involves a high processing delay. If the processing delay is too large, the signal may sound reverberant, similar to being in a bath room. Such a large delay is unsuitable for an ICC system.
Noise reduction is usually performed by filtering in the frequency-domain. With standard filterbank-based frequency domain methods, the low-delay requirements are typically not met because the filterbank introduces a relatively large delay. A common way to implement low-delay filtering is the so called overlap-save method. However, implementing time-invariant filtering using the overlap-save method is computationally expensive compared to commonly used filterbank methods. Methods have been proposed to reduce the complexity, however these methods are achieved at the cost of introducing slight signal distortions.
Basics of the Discrete Fourier Transformation (DFT)
The DFT and the inverse DFT can be performed with X=Fx and x=F−1X respectively. Here, x denotes the time-domain vector, X is the frequency-domain vector, and F denotes the DFT matrix with
      F    ⁢          ❘              k        ,        1              =      exp    ⁢                  {                              -            j                    ⁢                                    2              ⁢                                                          ⁢              π              ⁢                                                          ⁢              k              ⁢                                                          ⁢              l                        N                          }            .      If N is power of 2 the DFT can be performed efficiently by a Fast Fourier Transform (FFT).Multiplication in the Frequency Domain
It is known from Fourier theory that a convolution in time domain corresponds to a multiplication in frequency domain. In case of the DFT, this holds true only if one of the two signals is assumed to be a periodic signal with period length N where N is also the order of the DFT. This is called the cyclic convolution property of the DFT. In many practical applications, however, signals are not periodic. Hence, in general a multiplication in frequency domain does not lead to the same result as the time domain convolution. Therefore effects of cyclic convolution have to be avoided.
A large benefit of frequency domain processing is that a filtering operation can be realized simply by applying frequency dependent weights W(λ) to a spectrum X(λ)Y(λ)=W(λ)X(λ),  (1)rather than performing convolutions in time domain. Here, λ denotes the frequency index. Except for very low order filters, this reduces the processing load dramatically. To benefit from this efficient way of implementing a convolution, while obtaining the desired non-circular result, it must be ensured that the time-domain filter coefficients w(n)=IFFT{W(λ)} exhibit Q=N−P trailing zeros at the endw=[w(0), . . . , w(P−1),0, . . . , 0]T  (2)
If this is the case, the time-domain result y=IFFT{W(λ)X(λ)} contains P−1 samples [y(0), . . . , y(P−2)] which correspond to a cyclic convolution. The remaining Q+1 samples [y(P−1), . . . , y(N−1)] correspond to a non-cyclic convolution.
Finally, the following should be noted. Consider a filter vector w(n) with P coefficients different from zero, and wherein there are {tilde over (P)} non zero values at its end (these can be considered non-causal coefficients which reoccur at the end of the frame because of the cyclic property of the DFT.w=[w(0), . . . , w(P−{tilde over (P)}−1),0, . . . , 0,w(N−{tilde over (P)}), . . . , w(N−1)]T  (3)
In this case, the output samples that are free from cyclic convolution effects are[y(P−{tilde over (P)}−1), . . . , y(N−{tilde over (P)}−1)].  (4)Overlap-Save FilteringTime-Invariant Filtering
In order to save computational power, signal filtering can be performed in the frequency domain. Instead of sample-based convolution, the filtering in the frequency domain can be performed by multiplication. The basic structure of the overlap-save method is depicted in FIG. 1 (prior art). The signal x(n) is segmented 101 into frames x(k)=[x(k R), . . . , x(k R+N−1)]T of length N and processed on a frame by frame basis in the frequency domain with time index n and frame index k. Each R samples a new frame is processed (i.e. adjacent frames overlap by N−R). The time-domain segments x(k) are transformed 103 into frequency-domain vectors X(k)=F x(k). The filter vector w should have length N and shall exhibit Q zeros at the end as denoted in Eq. 2. It is transformed into the frequency domain by applying the DFT matrix FW=Fw.  (5)
The result is then applied 105 to the signal vectorsY(k)=WX(k)  (6)where the symbol {circle around (x)} stands for elementwise multiplication. As w obeys Eq. 2, the IFFT 107 of the filtered spectra Y(k), hence y(k)=F−1Y(k) has the property that its last Q+1 elements are valid in terms of corresponding to non-circular convolution. For obtaining the output signal stream yout(n) one block of R samples is extracted 109 from y(k)=[y(0, k), . . . , y(N−1, k)] for each frame k, e.g. yout(k R+n)=y(N/2+n, k) for 0≦n<R. If R≦Q+1 the correct (non-cyclic) convolution can be realized. If the filter vector doesn't change over time the operation in Eq. 5 can be calculated only once before start of the processing rather than for each frame.Time-Variant Filtering
There are also applications known where the filter is not fixed as described above. In J. J. Shynk: Frequency-domain and multirate adaptive filtering, IEEE Signal Processing Magazine, pp. 14-37, January 1992, which is hereby incorporated by reference herein, a frequency-domain adaptive filter method is described where the filter coefficients change due to updates in the frequency-domain {tilde over (W)}(k)=W(k−1)+Δ(k). This is realized by a constraint in the time-domain:W(k)=Fdiag{c}F−1{tilde over (W)}(k).  (7)
Multiplication with F and F−1 represents the application of the FFT and the inverse FFT, respectively. In Shynk, a rectangular window c=chard=[1, . . . , 1, 0, . . . , 0] with P=N/2 ones and Q=N/2 zeros is used. Applying this window sets the filter coefficients selectively to zero (hard constraint). As this operation has to be performed for each modification of {tilde over (W)} (i.e., for each filter update) this procedure can be quite expensive. Even applying the constraint matrix Chard=Fdiag{chard}F−1 directly in the frequency domain to the unconstrained filter {tilde over (W)}(k) can be expensive.
In order to save computations, alternatively, this procedure can be approximated in the frequency domain, as proposed by G. Enzner, P. Vary: A soft-partitioned frequency-domain adaptive filter for acoustic echo cancellation, Int. Conf. on Acoustics, Speech, and Signal Processing (ICASSP), 2003, which is hereby incorporated by reference herein. Here, a soft constraint is applied instead of a hard constraint. As opposed to a rectangular time-domain window with hard rectangular edges that reflect a hard constraint and cause spurious effects/leakage, a time-domain window function that represents a soft constraint has smooth transitions/edges. Illustratively, and without limitation, a Hann window wH(n) may be used. Other soft windows may also be utilized, as known in the art, such as, without limitation, a Hamming window, a cosine window, a Gaussian window, a Bartlett-Hann window, a Blackman window, a Kaiser Window, and other parametric windows.
The Hann Window wH(n) may have length P=N/2 and be zero-padded by Q=N/2 zeroscsoft=[wH(0), . . . , wH(P−1),0, . . . , 0]  (8)withwH(n)=½(1−cos(2πn/P).  (9)
The corresponding frequency-domain constraint matrixCsoft=Fdiag{csoft}F−1  (10)is a toeplitz matrix and exhibits neglectable values besides the main diagonal and some secondary diagonals. Setting these values to zero, the matrix-vector multiplication W=Csoft{tilde over (W)} reduces to a short convolution in frequency domain
                              W          ⁡                      (                          λ              ,              k                        )                          =                              ∑                          l              =                              -                L                                      L                    ⁢                                          ⁢                                                    C                soft                            ⁡                              (                l                )                                      ⁢                                                            W                  ~                                ⁡                                  (                                                            λ                      -                      l                                        ,                    k                                    )                                            .                                                          (        11        )            
The coefficients Csoft(l) are taken from the main and secondary diagonals of Csoft Csoft(l)=Csoft|n,n+1, for lε[−L, . . . , L].  (12)
The coefficients for L=3 and for the example setting from paragraph [0015] are (note that the symbol * indicates conjugate complex):Csoft(0)=0.25,  (13)Csoft(1)=C*soft(−1)=0.21221j,  (14)Csoft(2)=C*soft(−2)=0.125,  (15)Csoft(3)=C*soft(−3)=0.042441j.  (16)
The constraint matrix Csoft,approx that corresponds to the convolution in Eq. 11 is still a toeplitz matrix but sparse. FIG. 2 shows the exact time-domain constraint window csoft, as well as the effective window after the approximation Csoft,approx.
Time-Variant Filtering for Spectral Weighting
For the purposes of noise reduction it is desirable to specify a filter response directly in the frequency domain, where for each frequency bin λ a real-valued weighting factor is determined dynamically. Because of the real values, the time-domain representation of the filter is symmetric with respect to time index n=0 (considering a periodic extension of the buffer in both time directions). The filter weights may have been calculated with a certain filter characteristic which usually evaluates the signal-to-noise ratios of the different frequency bins. Examples for such filter characteristics can be found in G. Schmidt: Single-Channel Noise Suppression Based on Spectral Weighting—An Overview, Eurasip Newsletter, Vol. 15, No. 1, pp. 9-24, March 2004, which is hereby incorporated by reference it its entirety.
Illustratively, in a prior art in-car communication system, each frame k a vector of frequency-dependent filter weights {tilde over (W)}(k) was calculated by arbitrary filter characteristics. As the corresponding time domain filter is symmetric with respect to n=0 but the maximum of the time-domain constraint window from Eq. 8 is at N/4 and Chard from paragraph [0013] is also symmetric with respect to N/4, the filter coefficients were shifted in time by N/4 samples. This was performed in the frequency domain by applying a linear phase rotation{tilde over (W)}D(λ,k)=exp{−jπλ/2){tilde over (W)}(λ,k)=(−j)λ{tilde over (W)}(λ,k).  (17)
After that the approximated constraint matrix was appliedW(k)=Csoft,approx{tilde over (W)}D(k)  (18)
and the result in turn was applied to the input signal spectraY(k)=W(k)X(k).  (19)
The filtered time-domain signal buffer resulted as y(k)=F−1Y(k). R samples out of it have to be used as output signalYout(kR+n)=y(N/2+n,k), for nε[0, . . . , R−1]  (20)
The filter weights in Eq. 17 were modified by phase rotation in order to match to the location of the constraint window, aligned to time index 0. This phase rotation undesirably adds complexity into the system.